package com.example.graph;

import java.util.*;

/**
 * 单源最短路径问题
 * <p>
 * 有 n 个网络节点，标记为 1 到 n。
 * 给你一个列表 times，表示信号经过有向边的传递时间。 times[i] = (ui, vi, wi)，
 * 其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
 * 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
 * <p>
 * 示例 1：
 * 输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
 * 输出：2
 * <p>
 * 示例 2：
 * 输入：times = [[1,2,1]], n = 2, k = 1
 * 输出：1
 * <p>
 * 示例 3：
 * 输入：times = [[1,2,1]], n = 2, k = 2
 * 输出：-1
 * <p>
 * 提示：
 * 1 <= k <= n <= 100
 * 1 <= times.length <= 6000
 * times[i].length == 3
 * 1 <= ui, vi <= n
 * ui != vi
 * 0 <= wi <= 100
 * 所有 (ui, vi) 对都 互不相同（即，不含重复边）
 */
public class Leetcode743_NetworkDelayTime {
    public static void main(String[] args) {
        int[][] times = {
                {2, 6, 2}, {2, 5, 8},
                {6, 1, 6}, {6, 4, 2},
                {4, 1, 3}, {4, 3, 1}, {4, 5, 1},
                {5, 7, 3}, {1, 3, 3}, {3, 7, 2}
        };
        int n = 7;
        int k = 2;

//        times = new int[][] {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
//        n = 4;
//        k = 2;


        int time = new Solution().networkDelayTime(times, n, k);
        System.out.println(time);


    }

    static class Solution {
        public int networkDelayTime(int[][] times, int n, int k) {
            return networkDelayTime4(times, n, k);
        }

        /**
         * 解法一:DFS
         * <p>
         * 思路:
         * 深度优先搜索遍历从源节点出发到各个节点的所有路径，记录各条路径的长度
         * 找到从起始节点出发的所有路径，若遇到节点只要未出现在本次的路径之中，无论是否访问过，都需要扩展判断是否比当前路径值小
         * 1.使用数组记录当前从源节点出发到当前节点的最短距离，初始化为无穷大
         * 2.从源节点出发，记录当前路径的长度，如果小于到达节点当前的最短距离，则进行更新
         * 剪枝：如果当前节点的最短距离比当前路径长度要短，可以不用在本次继续扩展该节点
         *
         * @param times      信号经过有向边的传递时间
         * @param n          节点的个数
         * @param sourceNode 开始节点
         * @return
         */
        public int networkDelayTime1(int[][] times, int n, int sourceNode) {
            // 1.首先根据给出的times构建出邻接表并完成初始化工作
            /*
            顶点为key,顶点能到的其他顶点组成的List为value value为数组，value[0]为邻居节点，value[1]为两个顶点之间路径的权重
            邻接表:
            2 -> [[6, 2], [5, 8]]
            6 -> [[1, 6], [4, 2]]
            4 -> [[1, 3], [3, 1], [5, 1]]
            5 -> [[7, 3]]
            1 -> [[3, 3]]
            3 -> [[7, 2]]
            */
            Map<Integer, List<int[]>> adj = new HashMap<>();
            for (int i = 0; i < times.length; i++) {
                adj.computeIfAbsent(times[i][0], key -> new ArrayList<>()).add(new int[]{times[i][1], times[i][2]});
            }
            // dist 存储从源节点sourceNode 到各个节点的最短距离 dist[i] = m,表示源节点到i的权重为m
            int dist[] = new int[n + 1];
            //初始化最短距离为无穷大
            for (int i = 1; i <= n; i++) {
                dist[i] = Integer.MAX_VALUE;
            }

            // 2.从起始节点开始 dfs
            dfs(adj, sourceNode, 0, dist);

            // 3.寻找最短路径中的最大值并返回
            int res = 0;
            for (int i = 1; i <= n; i++) {
                if (dist[i] == Integer.MAX_VALUE) // 说明图不是连通图
                    return -1;
                res = Math.max(res, dist[i]);
            }
            return res;
        }

        /**
         * 迪杰斯特拉算法(广度优先+贪心)
         * <p>
         * 其主要特点是以起始点为中心向外层层扩展(广度优先)，直到扩展到终点为止。
         * <p>
         * 定义一个节点集合visited表示从源点 sourceNode 出发已经确定最短路径的节点
         * 那么下一个可以确定最短路径的节点一定是与 visited 集合(中为true的节点)直接相连的节点(即visited集合之外(visited[i] = false))
         * <p>
         * 即每次BFS都要将所有在visited集合之外(visited[i] = false)并且与当前visited集合之中直接相连的节点都要算一遍
         *
         * @param times
         * @param n
         * @param sourceNode
         * @return
         */
        public int networkDelayTime2(int[][] times, int n, int sourceNode) {
            // 1. 构建邻接表和初始化最短距离数组
            Map<Integer, List<int[]>> adj = new HashMap<>();
            for (int i = 0; i < times.length; i++) {
                adj.computeIfAbsent(times[i][0], key -> new ArrayList<>())
                        .add(new int[]{times[i][1], times[i][2]});
            }
            // dist 存储从源节点sourceNode 到各个节点的最短距离 dist[i] = m,表示源节点到i的权重为m
            int dist[] = new int[n + 1];
            //初始化最短距离为无穷大
            for (int i = 1; i <= n; i++) {
                dist[i] = Integer.MAX_VALUE;
            }
            dist[sourceNode] = 0;
            boolean[] visited = new boolean[n + 1];// 已经确定最短路径顶点的集合true表示已经确定，false表示未确定

            // 2. bfs + 贪心(迪杰斯特拉算法)确定最短路径
            while (true) {
                int node = -1;
                int distance = Integer.MAX_VALUE;

                for (int i = 1; i <= n; ++i) {
                    if (!visited[i] && dist[i] < distance) {
                        distance = dist[i];
                        node = i;
                    }
                }
                if (node < 0) // 当所有的顶点都已加入到visited集合中(visited所有元素都为true)
                    break;
                visited[node] = true;
                if (adj.get(node) != null) {
                    for (int j = 0; j < adj.get(node).size(); j++) {
                        int[] tmp = adj.get(node).get(j);
                        dist[tmp[0]] = Math.min(dist[tmp[0]], dist[node] + tmp[1]);
                    }
                }
            }

            // 3. 寻找最短路径中的最大值并返回
            int res = 0;
            for (int i = 1; i <= n; i++) {
                if (dist[i] == Integer.MAX_VALUE) // 说明图不是连通图
                    return -1;
                res = Math.max(res, dist[i]);
            }
            return res;
        }


        /**
         * 迪杰斯特拉(最小堆实现)
         *
         * @param times
         * @param n
         * @param sourceNode
         * @return
         */
        public int networkDelayTime3(int[][] times, int n, int sourceNode) {
            // 构建邻接表
            Map<Integer, List<int[]>> adj = new HashMap();
            for (int[] edge : times) {
                adj.computeIfAbsent(edge[0], key -> new ArrayList<>())
                        .add(new int[]{edge[1], edge[2]});
            }
            Queue<int[]> minHeap = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
            // int[0]: 从k到达的节点的权重 ;int[1] 从k到达的节点
            minHeap.offer(new int[]{0, sourceNode});// 先将从sourceNode到打sourceNode放入最小堆中进行初始化

            Map<Integer, Integer> dist = new HashMap(); // k到达节点key的最短路径为对应的value

            while (!minHeap.isEmpty()) {
                int[] info = minHeap.poll();
                int distance = info[0], node = info[1];
                if (dist.containsKey(node))
                    continue;
                dist.put(node, distance);
                if (adj.containsKey(node))
                    for (int[] tmp : adj.get(node)) {
                        int tmpNode = tmp[0], tmpDist = tmp[1];
                        if (!dist.containsKey(tmpNode))
                            minHeap.offer(new int[]{distance + tmpDist, tmpNode});
                    }
            }

            if (dist.size() != n) return -1;
            int ans = 0;
            for (int cand : dist.values())
                ans = Math.max(ans, cand);
            return ans;
        }


        /**
         * Bellman-ford 算法
         * Bellman-ford 算法比dijkstra算法更具普遍性，因为它对边没有要求，可以处理负权边与负权回路。
         * 缺点是时间复杂度过高，高达O(VE), V为顶点数，E为边数。
         *
         * 主要思想:
         * 对所有的边进行n-1轮松弛操作(动态规划)，
         * 因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含 n-1 边。
         * 换句话说，第1轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离；（相当于动态规划的初始化状态）
         * 第2轮在对所有的边进行松弛后，得到的是源点最多经过两条边到达其他顶点的最短距离；
         * 第3轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离
         * 第 n-1 轮在对所有的边进行松弛后，得到的是源点最多经过 n-1 条边到达其他顶点的最短距离
         *
         * 实现:
         *   1.原问题与子问题:
         *     求解经过 i 次中转能到达各个节点的最短路径
         *
         *   2.设计状态:
         *     dp[i][j] = m 表示从源节点(src) 中间经过 j 个顶点 到顶点 i 的最短路径为m
         *
         *   3.松弛操作(状态转移方程):
         *
         *   4.边界值:
         *     dp[src][i] = 0(0 <= i < n) 从 src 到 src 不管经过多少次中转最短路径都是0
         *
         *
         * @param n
         * @param times
         * @param sourceNode
         * @return
         */
        public int networkDelayTime4(int[][] times, int n, int sourceNode) {
            int[][] dp = new int[n + 1][n]; // dp[i][j] = m 表示从 源节点(src) 中间经过 j 个顶点 到 i 的最短路径为m
            // 初始化 1：由于找最短路径，因此初始化的时候赋值成为一个不可能的较大的值
            for (int i = 1; i < dp.length; i++) {
                for (int j = 0; j < dp[0].length; j++) { // 只有终点也是sourceNode的节点最短路径初始化为0，其余都初始化为最大值
                    dp[i][j] = i == sourceNode ? 0 : Integer.MAX_VALUE;
                }
            }
            // 打印初始状态
//            for (int[] ints : dp) {
//                for (int anInt : ints) {
//                    System.out.print(anInt + ", ");
//                }
//                System.out.println();
//            }

            // 第 1 轮松弛操作，只需要对从 src 出发的边进行松弛操作(初始化)
            for (int[] time : times) {
                if (time[0] == sourceNode) {
                    dp[time[1]][0] = time[2];
                }
            }

            // 第 2 轮到第 n - 1 轮松弛操作，最后一轮松弛操作是为了检测是否可达
            for (int i = 1; i < n; i++) {
                for (int[] time : times) {
                    int from = time[0];
                    int to = time[1];
                    // 每一次松弛操作的结果是互相独立的，因此只有在上一轮（第 i - 1 轮）得到单源最短路径的顶点，才需要执行松弛操作
                    if (dp[from][i - 1] != Integer.MAX_VALUE) {
                        dp[to][i] = Math.min(dp[from][i - 1] + time[2], dp[to][i]);
                    }
                }
            }

            // 打印计算完毕的状态
//            System.out.println("========================");
//            for (int[] ints : dp) {
//                for (int anInt : ints) {
//                    System.out.print(anInt + ", ");
//                }
//                System.out.println();
//            }

            // 如果不可达，返回 -1
            int res = 0;
            for (int i = 1; i <= n; i++) {
                if (dp[i][n - 1] == Integer.MAX_VALUE) return -1;
                res = Math.max(res, dp[i][n - 1]);
            }
            // 返回最终结果
            return res;
        }

        /**
         * @param adj      邻接矩阵
         * @param node     当前源节点到达的目标节点
         * @param distance 源节点到当前节点的距离
         * @param dist     源节点sourceNode到各个节点的最短距离
         */
        private void dfs(Map<Integer, List<int[]>> adj, int node, int distance, int[] dist) {
            // 剪枝：若之前存在更快到达node节点的路径，本次无需继续扩展该节点
            if (distance >= dist[node]) return;
            dist[node] = distance;

            if (adj.get(node) != null) {
                for (int i = 0; i < adj.get(node).size(); i++) {
                    int[] tmp = adj.get(node).get(i);
                    dfs(adj, tmp[0], tmp[1] + distance, dist);
                }
            }
        }
    }
}

